COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00019 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a46.tex[154,phy] \today\hfill}

\bigskip
\line{\bf Pairing Functions \hfil}

\smallskip
In this section, it is convenient to identify the strings over
$\Sigma=\{a↓1,a↓2,\ldots,a↓n\}$ with integers, by taking the strings
in order of increasing length, and in alphabetical order for each
length, as illustrated below:
$$\vcenter{\halign{$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\cr
0&1&2&3&4&5&6&7&8&9\cr
\epsilon&a&b&aa&ab&ba&bb&aaa&aab&aba\cr}}$$
The function from strings to integers is defined by induction:
$$\eqalign{{\rm number}(\epsilon)&=0\cr
{\rm number}(xa↓i)&={\rm number}(x)\times n+i\,.\cr}$$
This is called an $n${\sl -adic\/} numbering. We say that a function
on strings is monotone, or that one string is greater than another,
as a shorthand for talking about their associated numbers.

A {\sl pairing function\/} for strings over~$\Sigma$ is a one-to-one computable
function that maps $\Sigma↑{\ast}\times\Sigma↑{\ast}$ onto $\Sigma↑{\ast}-
\epsilon$. Calling the pairing function~$\pi$, $\pi(x,y)≠\epsilon$;
$\pi(x,y)=\pi(u,v)$ iff $x=u$, $y=v$; and
$(\forall z\mid z≠\epsilon)(\exists x,y)[\pi(x,y)=z]$.
A~pairing function is {\sl monotone\/} if $x↓1≤x↓2$, $y↓1≤y↓2⊃\pi(x↓1,y↓1)
≤\pi(x↓2,y↓2)$. The {\sl projection functions\/} of~$\pi$ are functions
$\alpha$, $\beta$ such that $\alpha\bigl(\pi(x,y)\bigr)=x$,
$\beta\bigl(\pi(x,y)\bigr)=y$. To make $\alpha$ and~$\beta$ total, we may
define $\alpha(\epsilon)=\beta(\epsilon)=\epsilon$.

\smallskip
\display 38pt::{\bf Drill:}
Show that $\alpha$ and $\beta$ are unique and computable.

\smallskip
\display 38pt::{\bf Drill:}
Assume $\pi$ is monotone. Show that $\alpha$ and $\beta$ are monotone,
$\pi(x,y)>x+y$, $\alpha(z)<z$ unless $z=\epsilon$, $\pi(\epsilon,\epsilon)
=a↓1$.

\smallskip
Examples of monotone pairing functions are

$$\vbox{\offinterlineskip
\halign{$#$&$#$&$#$&\vrule#&\strut\xskip\hfil$#$%
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$\xskip
&\hbox{\qquad}$#$\xskip%
&\vrule#&\strut\xskip\hfil$#$%
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$\xskip\cr
&&y&\omit&&&\pi↓1&&&&&\omit&&&\pi↓2\cr
x&&&\omit&0&1&2&3&4&&&\omit&0&1&2&3&4\cr
&&&\multispan7\hrulefill&&\multispan7\hrulefill\cr
&&&height2pt&\omit&\omit&\omit&\omit&\omit&\omit&\omit&&\omit&\omit&\omit%
&\omit&\omit&\omit\cr
&0&&&1&3&5&7&9&\ldots&0&&1&4&9&16&\ldots\cr
&1&&&2&6&10&14&18&\ldots&1&&2&3&8&15&\ldots\cr
&2&&&4&12&20&28&36&\ldots&2&&5&6&7&14&\ldots\cr
&3&&&8&24&40&56&\ldots&&3&&10&11&12&13&\ldots\cr
&4&&&16&48&80&\ldots&&&4&&17&18&\ldots\cr
}}$$
$$\vbox{\offinterlineskip
\halign{\hfil$#$\xskip&\vrule#&\strut\xskip\hfil$#$%
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$
&\xskip\hfil$#$\xskip\cr
&\omit&&&\pi↓3\cr
&\omit&0&1&2&3&4\cr
&\multispan7\hrulefill\cr
&height2pt\cr
0&&1&3&6&10&15&\ldots\cr
1&&2&5&9&14&\ldots\cr
2&&4&8&13&\ldots\cr
3&&7&12&18\cr
4&&11&17\cr
5&&16\cr
}}$$


\noindent
defined by:
$$\eqalign{\pi↓1(x,y)&=2↑x(2y+1)\cr
\noalign{\smallskip}
\pi↓2(x,y)&=m↑2+m+1+y-x\,,\hbox{ where $m=\max(x,y)$}\cr
\noalign{\smallskip}
\pi↓3(x,y)&={(x+y+1)(x+y+2)\over 2}-x\cr}$$
\smallskip
\display 38pt::{\bf Drill:}
The above are defined on the natural numbers. How would they be defined on
strings?

\smallskip
\display 38pt::{\bf Drill:}
How does one compute $\alpha$ and $\beta$ for each of the above pairing
functions?

\bigskip

\line{\bf Lists\hfill}

{\sl Lists\/} are defined in terms of a pairing function. The list
$\langle x↓1,x↓2,\ldots,x↓n\rangle$ is $x↓1\pi\bigl(x↓2\pi\bigl(x↓3\pi\bigl(
\ldots$ \break
$\pi(x↓n\pi\,\epsilon)\bigr)\bigr)\bigr)\ldots\bigr)\bigr)$.
Important facts are:
$$\eqalign{&\langle\;\rangle =\epsilon\cr
&\langle x↓1\rangle=x↓1\pi\epsilon\cr
&\alpha(\langle x↓1,\ldots,x↓n\rangle)=x↓1\cr
&\beta(\langle x↓1,\ldots,x↓n\rangle)=\langle x↓2,x↓3,\ldots,x↓n\rangle\,.\cr}$$
To get the $i$th element of a list, use $\alpha\bigl(\beta↑{i-1}(x)\bigr)$,
abbreviated~$x↓i$.

\medskip
\display 38pt::{\bf Drill:}
Show that if $\pi$ is monotone every number is a list in exactly one way.

\medskip
To get the reverse $R=\langle x↓n,x↓{n-1},\ldots,x↓2,x↓1\rangle$ of
list~$L$, use this program:

\medskip
\halign{\qquad\qquad #\hfil\cr
$T←L$; $R←\langle\;\rangle$;\cr
WHILE $T≠\langle\;\rangle$ DO\cr
\qquad BEGIN\cr
\qquad $R←\alpha(T)\pi\,R$;\cr
\qquad $T←\beta(T)$\cr
\qquad END;\cr}

\medskip
\display 38pt::{\bf Drill:}
Program concatenation of lists.

\medskip
A list can be used as a stack, an array, a set, or a queue.

\medskip
\display 20pt:$\bullet$:
Lists as stacks:

\medskip
\display 40pt::
To use list $L$ as a stack $S$, translate:

\medskip
\halign{\hskip 40pt #\hfil\quad&#\hfil\quad&$#$\hfil\cr
$S$ empty?&to&L=\epsilon\,?\cr
Push $x$ on $S$&to&L←x\pi L\cr
Top($S$)&to&\alpha(L)\cr
Pop($S$)&to&L←\beta(L)\cr}

\medskip
\display 20pt:$\bullet$:
Lists as arrays:

\medskip
\display 40pt::
To use list $L$ as an array $A$, let its elements be ordered pairs
$i\pi A↓i$. Translate:

\medskip
\halign{\hskip 40pt #\hfil\quad&#\hfil\quad&#\hfil\cr
$x←A↓i$&to&$T←L\,$;\cr
&&WHILE $\alpha\bigl(\alpha(T)\bigr)≠i$ DO\cr
&&\qquad $T←\beta(T)$;\cr
&&$x←\beta\bigl(\alpha(T)\bigr)$\cr
$A↓i←x$&to&$L←(i\pi x)\pi L$\cr}

\vfill\eject

\display 20pt:$\bullet$:
Lists as sets:

\medskip
\display 40pt::
To use list $L$ as a set $S$, translate 

\medskip
\halign{\hskip 40pt #\hfil\quad&#\hfil\quad&#\hfil\cr
$x\in S$?&to&$T←L$;\cr
&&FLAG $←$ FALSE;\cr
&&WHILE $T≠\langle\;\rangle$ DO\cr
&&\qquad BEGIN\cr
&&\qquad IF $\alpha(T)=x$ THEN FLAG $←$ TRUE;\cr
&&\qquad $T←\beta(T)$\cr
&&\qquad END;\cr
&& FLAG?\cr
\noalign{\smallskip}
Add $x$ to $S$&to&$L←x\pi L$\cr
\noalign{\smallskip}
Delete $x$ from $S$&to&$T←\langle\;\rangle$;\cr
&&WHILE $S≠\langle\;\rangle$ DO\cr
&&\qquad BEGIN\cr
&&\qquad IF $\alpha(S)≠X$ THEN\cr
&&\qquad\qquad $T←\alpha(S)\pi T$;\cr
&&\qquad $S←\beta(S)$\cr
&&\qquad END\cr
&&$S←T$\cr
\noalign{\smallskip}
FOR $x\in S$ DO $Y$&to&$T←S$;\cr
&&WHILE $T≠\langle\;\rangle$ DO\cr
&&\qquad BEGIN\cr
&&\qquad $x←\alpha(T)$;\cr
&&\qquad $Y$;\cr
&&\qquad Delete $x$ from $T$\cr
&&\qquad END\cr}

\display 20pt:$\bullet$:
Lists as queues:

\display 40pt::
To use list $L$ as a queue $K$ is much like simulating a stack, except that
we must be able to append a~new element at the right end, an operation
called appending. Translate

\halign{\hskip 40pt #\hfil\quad&#\hfil\quad&#\hfil\cr
Append $x$ to $K$&into&$T←{\rm Reverse}(K)$;\cr
&&$T=x\pi T$\cr
&&$K←{\rm Reverse}(T)$.\cr}

\vfill\eject

\line{\bf Universal Machines and Decision Problems\hfill}

A transition of a machine may be represented by $\langle q,a,q'\rangle$,
where $q$ and~$q'$ are states and $a$ is one of a finite set of possible
actions or test outcomes, like read~0, read~1, write~0, write~1,
push~0 on stack$↓1$, pop~0 from stack$↓2$, stack$↓1$ empty,
stack$↓1$ nonempty. The machine's set of
transitions~$\delta$ can be
represented by a list. The sets of initial
and accepting states can each be represented by a list. The entire
machine can be represented by $\langle S,F,\delta\rangle$.
A~history or computation can be represented as a list 
$\langle q↓0,t↓1,t↓2,\ldots,t↓n\rangle$, where $q↓0$ is the starting
state and the $t↓i$ are the transitions taken. To test whether $c$ is
a~computation, test that $q↓0\in S$, that successive transitions are linked
($t↓{i,3}=t↓{i+1,1}$), that the computation ends in~$F$ ($t↓{n,3}\in F$),
and that the actions of each memory device are consistent. All are
readily programmed.

A {\sl universal\/} program $U(M,x)$ for a particular type of machine
reads the  representation for a machine~$M$, followed by an input
string~$x$. It then generates all possible strings until it finds one,~$c$,
that is a computation of~$M$ and that reads the characters of~$x$. It
accepts $M\otimes x$ if and only if there is a computation of~$M$ that
accepts~$x$; if not, it runs forever. A~universal program is deterministic,
even if simulating nondeterministic machines.
We can readily construct universal programs for one-tape machines, 
two-stack machines, two-counter machines, etc.\ (call them, generically,
Turing machines). 

A {\sl decision\/} program for a particular type of machine reads $M$
and~$x$ as above, and determines somehow whether there is a (complete)
computation of~$M$ on input~$x$. It halts, accepting or rejecting according
as~$M$ has a computation that accepts~$x$.
Suppose we could construct a decision program.
Then  we could construct a paradoxical program,
called {\tt BARBER} after the classic Russell paradox. {\tt BARBER}
reads its entire input,~$x$. If $x$ is not the representation of a machine~$M$,
it rejects~$x$. Otherwise, it uses the decision program to see if $M$ accepts
input~$x$. If $M$ accepts~$x$, {\tt BARBER} rejects~$x$. If $M$ does not
accept~$x$, {\tt BARBER} accepts~$x$.

Now let $B$ be the list that represents {\tt BARBER}. Let {\tt BARBER}
read~$B$. The machine~($M$) that $B$ represents is {\tt BARBER} itself.
If {\tt BARBER} ($=M$) accepts~$B$ ($=x$), {\tt BARBER} rejects~$B$.
If {\tt BARBER} rejects (and therefore does not accept)~$B$, {\tt BARBER}
accepts~$B$. {\tt BARBER} must either accept or reject~$B$, because it
always halts, and not both, because it is deterministic. We are at the
mercy of an absurdity. The only gratuitous assumption we made, the existence
of a decision program for Turing machines, must be false.

\smallskip
\display 38pt::{\bf Drill:}
There are deterministic programs for, say, NPDMs. Why doesn't that lead
to a similar paradox?


\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd.
First draft (not published)
May 28, 1986.
%revised date;
%subsequently revised.

\bye